package question.solution23;
import	java.util.PriorityQueue;

import java.util.List;
import java.util.Queue;

public class Solution23 {

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists1(ListNode[] lists) {
        ListNode head = new ListNode();
        ListNode tail = head;
        ListNode minNode = getMinNode(lists);
        while(minNode != null){
            tail.next = minNode;
            tail = minNode;
            minNode = getMinNode(lists);
        }

        return head.next;
    }

    private ListNode getMinNode(ListNode[] lists){
        ListNode minNode = new ListNode(Integer.MAX_VALUE);
        int minNodeIndex = -1;
        for(int i=0;i<lists.length; i++){
            ListNode node = lists[i];
            if(node == null){
                continue;
            }
            if(node.val < minNode.val){
                minNodeIndex = i;
                minNode = lists[i];
            }
        }
        if(minNodeIndex >= 0){
            minNode = lists[minNodeIndex];
            lists[minNodeIndex] = minNode.next;
            return minNode;
        }
        return null;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        Queue<ListNode> pq = new PriorityQueue<ListNode> ((v1, v2) -> v1.val - v2.val);
        for(ListNode node : lists){
            if(null != node){
                pq.offer(node);
            }
        }

        ListNode head = new ListNode(0);
        ListNode tail = head;
        while(!pq.isEmpty()){
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = minNode;
            if(minNode.next != null){
                pq.offer(minNode.next);
            }
        }
        return head.next;
    }



    public boolean test() {
//        [
//        1->4->5,
//        1->3->4,
//        2->6
//        ]
        ListNode[] testArray = new ListNode[3];
        ListNode listNode15 = new ListNode(5,null);
        ListNode listNode14 = new ListNode(4,listNode15);
        ListNode listNode11 = new ListNode(1,listNode14);
        ListNode listNode24 = new ListNode(4,null);
        ListNode listNode23= new ListNode(3,listNode24);
        ListNode listNode21 = new ListNode(1,listNode23);
        ListNode listNode36 = new ListNode(6,null);
        ListNode listNode32 = new ListNode(2,listNode36);
        testArray[0]=listNode11;
        testArray[1] = listNode21;
        testArray[2] = listNode32;

//        ListNode[] testArray = new ListNode[1];
        ListNode result = mergeKLists2(testArray);
        return true;
    }

}
